import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @作者 zxy
 * @时间 2023-04-03 16:45
 * @说明 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class Solution {
    /**
     * 执行用时：6 ms, 在所有 Java 提交中击败了97.24%的用户
     * 内存消耗：45.8 MB , 在所有 Java 提交中击败了92.91%的用户
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        int[] record = new int[10001];
        List<Integer> same = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] == intervals[i][1]) {
                same.add(intervals[i][0]);
            }
            for (int i1 = intervals[i][0]; i1 < intervals[i][1]; i1++) {
                record[i1] = 1;
            }
        }
        List<Integer[]> list = new ArrayList<>();

        int[] record1 = new int[10001];
        int start = 0;
        boolean isRecord = false;
        for (int i = 0; i < record.length; i++) {
            if (record[i] == 1) {
                if (!isRecord) {
                    isRecord = true;
                    start = i;
                }
            } else {
                if (isRecord) {
                    record1[i] = 1;
                    list.add(new Integer[]{start, i});
                    isRecord = false;
                }
            }
        }
        int delNum = 0;
        for (int i = 0; i < same.size(); i++) {
            if (record[same.get(i)] != 1 && record1[same.get(i)] != 1) {
                delNum++;
                list.add(new Integer[]{same.get(i), same.get(i)});
            }
        }

        int[][] res = new int[list.size() - delNum][2];
        for (int i = 0, j = 0; i < res.length; i++, j++) {
            if (Objects.equals(list.get(j)[0], list.get(j)[1]) && record1[list.get(j)[0]] == 1) {
                i--;
            } else {
                res[i][0] = list.get(j)[0];
                res[i][1] = list.get(j)[1];
            }
        }
        return res;
    }
}
